package cuit.epoch.pymjl;

/**
 * @author Pymjl
 * @version 1.0
 * @date 2022/10/11 13:57
 **/
public class QuickSort {
    private int[] array;

    public QuickSort(int[] array) {
        this.array = array;
    }

    public void sort() {
        quickSort(array, 0, array.length - 1);
    }

    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    /**
     * 递归排序
     *
     * @param src
     * @param begin
     * @param end
     */
    private void quickSort(int[] src, int begin, int end) {
        if (begin < end) {
            int key = src[begin];
            int i = begin;
            int j = end;
            while (i < j) {
                while (i < j && src[j] < key) {
                    j--;
                }
                if (i < j) {
                    src[i] = src[j];
                    i++;
                }
                while (i < j && src[i] > key) {
                    i++;
                }
                if (i < j) {
                    src[j] = src[i];
                    j--;
                }
            }
            src[i] = key;
            quickSort(src, begin, i - 1);
            quickSort(src, i + 1, end);
        }
    }

    public void quicksort(int[] array, int begin, int end) {
        if (begin < end) {
            //找到基准值，以数组第一个元素为基准值
            int key = array[begin];
            //定义起始指针和结束指针
            int i = begin, j = end;
            //开始快排
            while (i < j) {
                //如果比基准值大，放在左边
                while (i < j && array[j] < key) {
                    j--;
                }
                //将数据放在左边
                if (i < j) {
                    array[i] = array[j];
                    i++;
                }
                //如果比基准值小，放在右边
                while (i < j && array[i] > key) {
                    i++;
                }
                //将较小的数据放在右边
                if (i < j) {
                    array[j] = array[i];
                    j--;
                }
            }
            //遍历完后将中间的值重新设置回基准值
            array[i] = key;
            //然后进入递归排序
            quicksort(array, begin, i - 1);
            quicksort(array, i + 1, end);
        }
    }

    public static void main(String[] args) {
        int[] array = {47, 29, 71, 99, 78, 19, 24, 47};
        QuickSort quickSort = new QuickSort(array);
        quickSort.sort();
        quickSort.print();
    }
}
